package com.cwj;

import java.util.*;

public class Dijkstra {

    /**
     * arr[0] = a
     * arr[1] = b
     * arr[2] = 权值
     * n为点的个数
     * start 为起始点
     */
    public void solution(int[][] grid, int n, int start) {
        List<int[]>[] list = new List[n];
        int max = 0x7fffffff;
        int[] distance = new int[n];
        Arrays.fill(distance, max);
        distance[start] = 0;
        for (int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        for (int[] arr : grid) {
            list[arr[0]].add(new int[]{arr[1], arr[2]});
            list[arr[1]].add(new int[]{arr[0], arr[2]});
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(a -> distance[a]));
        pq.add(start);
        while (!pq.isEmpty()) {
            int cur = pq.poll();
            for (int[] next : list[cur]) {
                if (distance[next[0]] > next[1] + distance[cur]) {
                    distance[next[0]] = next[1] + distance[cur];
                    pq.add(next[0]);
                }
            }
        }
        //最终得到distance数组
    }


}
